package LeetCode;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:14
 */
public class interview34 {

     public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
     }

    //全局变量
    List<List<Integer>> result = new LinkedList<>();//使用队列可以很好的先进先出
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode tree,int sum){
        searchPath(tree,sum);
        return result;
    }

    public void searchPath(TreeNode treeNode,int sum){
        if (treeNode==null){
            return;
        }
        path.add(treeNode.val);
        sum-=treeNode.val;
        if (sum == 0 && (treeNode.left==null&&treeNode.right==null)){
            result.add(path);
        }
        searchPath(treeNode.left,sum);
        searchPath(treeNode.right,sum);
        path.removeLast();
    }

}
